<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>4. 归并排序 | 被删的前端游乐场</title>
    <meta name="generator" content="VuePress 1.8.2">
    
    <meta name="description" content="Just playing around">
    
    <link rel="preload" href="/front-end-playground/assets/css/0.styles.6ad2a9ca.css" as="style"><link rel="preload" href="/front-end-playground/assets/js/app.1e2670bf.js" as="script"><link rel="preload" href="/front-end-playground/assets/js/2.38d016d1.js" as="script"><link rel="preload" href="/front-end-playground/assets/js/3.e3f029cb.js" as="script"><link rel="preload" href="/front-end-playground/assets/js/21.6130b6a1.js" as="script">
    <link rel="stylesheet" href="/front-end-playground/assets/css/0.styles.6ad2a9ca.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/front-end-playground/" class="home-link router-link-active"><!----> <span class="site-name">被删的前端游乐场</span></a> <div class="links"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><a href="/front-end-playground/" class="nav-link">概述</a></div><div class="nav-item"><a href="/front-end-playground/front-end-basic/" class="nav-link">前端领域</a></div><div class="nav-item"><a href="/front-end-playground/vue/" class="nav-link">Vue学习</a></div><div class="nav-item"><a href="/front-end-playground/wxapp/" class="nav-link">小程序学习</a></div><div class="nav-item"><a href="/front-end-playground/front-end-others/" class="nav-link">百家齐放</a></div><div class="nav-item"><a href="/front-end-playground/front-end-addon/" class="nav-link router-link-active">前端的进击</a></div><div class="nav-item"><a href="/front-end-playground/front-end-work/" class="nav-link">前端与工作</a></div><div class="nav-item"><a href="/front-end-playground/faq.html" class="nav-link">FAQ</a></div> <a href="https://github.com/godbasin/front-end-playground" target="_blank" rel="noopener noreferrer" class="repo-link">
    Github
    <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><nav class="nav-links"><div class="nav-item"><a href="/front-end-playground/" class="nav-link">概述</a></div><div class="nav-item"><a href="/front-end-playground/front-end-basic/" class="nav-link">前端领域</a></div><div class="nav-item"><a href="/front-end-playground/vue/" class="nav-link">Vue学习</a></div><div class="nav-item"><a href="/front-end-playground/wxapp/" class="nav-link">小程序学习</a></div><div class="nav-item"><a href="/front-end-playground/front-end-others/" class="nav-link">百家齐放</a></div><div class="nav-item"><a href="/front-end-playground/front-end-addon/" class="nav-link router-link-active">前端的进击</a></div><div class="nav-item"><a href="/front-end-playground/front-end-work/" class="nav-link">前端与工作</a></div><div class="nav-item"><a href="/front-end-playground/faq.html" class="nav-link">FAQ</a></div> <a href="https://github.com/godbasin/front-end-playground" target="_blank" rel="noopener noreferrer" class="repo-link">
    Github
    <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav>  <ul class="sidebar-links"><li><section class="sidebar-group collapsable depth-0" style="padding-top:;"><!----> <p class="sidebar-heading"><span>不止单线程</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0" style="padding-top:10px;"><div class="kitty-main" data-v-2b653b36><span class="stand" data-v-2b653b36></span> <div class="cat" data-v-2b653b36><div class="body" data-v-2b653b36></div> <div class="head" data-v-2b653b36><div class="ear" data-v-2b653b36></div> <div class="ear" data-v-2b653b36></div></div> <div class="face" data-v-2b653b36><div class="nose" data-v-2b653b36></div> <div class="whisker-container" data-v-2b653b36><div class="whisker" data-v-2b653b36></div> <div class="whisker" data-v-2b653b36></div></div> <div class="whisker-container" data-v-2b653b36><div class="whisker" data-v-2b653b36></div> <div class="whisker" data-v-2b653b36></div></div></div> <div class="tail-container" data-v-2b653b36><div class="tail" data-v-2b653b36><div class="tail" data-v-2b653b36><div class="tail" data-v-2b653b36><div class="tail" data-v-2b653b36><div class="tail" data-v-2b653b36><div class="tail" data-v-2b653b36><div class="tail" data-v-2b653b36></div></div></div></div></div></div></div></div></div></div> <p class="sidebar-heading open"><span>简单算法之 js 实现</span> <span class="arrow down"></span></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/front-end-playground/front-end-addon/simple-algorithm/1-bubble-sort.html" class="sidebar-link">1. 冒泡排序</a></li><li><a href="/front-end-playground/front-end-addon/simple-algorithm/2-counting-sort.html" class="sidebar-link">2. 计数排序</a></li><li><a href="/front-end-playground/front-end-addon/simple-algorithm/3-insertion-sort.html" class="sidebar-link">3. 插入排序</a></li><li><a href="/front-end-playground/front-end-addon/simple-algorithm/4-merge-sort.html" aria-current="page" class="active sidebar-link">4. 归并排序</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/front-end-playground/front-end-addon/simple-algorithm/4-merge-sort.html#排序问题" class="sidebar-link">排序问题</a></li><li class="sidebar-sub-header"><a href="/front-end-playground/front-end-addon/simple-algorithm/4-merge-sort.html#思路" class="sidebar-link">思路</a></li><li class="sidebar-sub-header"><a href="/front-end-playground/front-end-addon/simple-algorithm/4-merge-sort.html#js-实现" class="sidebar-link">js 实现</a></li><li class="sidebar-sub-header"><a href="/front-end-playground/front-end-addon/simple-algorithm/4-merge-sort.html#验证" class="sidebar-link">验证</a></li></ul></li><li><a href="/front-end-playground/front-end-addon/simple-algorithm/5-quick-sort.html" class="sidebar-link">5. 快速排序</a></li><li><a href="/front-end-playground/front-end-addon/simple-algorithm/6-heap-sort.html" class="sidebar-link">6. 堆排序</a></li><li><a href="/front-end-playground/front-end-addon/simple-algorithm/7-quick-select.html" class="sidebar-link">7. 快速选择</a></li><li><a href="/front-end-playground/front-end-addon/simple-algorithm/8-find-maximum-subarray.html" class="sidebar-link">8. 分治法求最大子数组</a></li><li><a href="/front-end-playground/front-end-addon/simple-algorithm/9-n-n-matrix.html" class="sidebar-link">9. n×n 矩阵计算</a></li></ul></section></li><li><section class="sidebar-group collapsable depth-0" style="padding-top:;"><!----> <p class="sidebar-heading"><span>不止纯前端</span> <span class="arrow right"></span></p> <!----></section></li></ul> </aside> <main class="page"> <div class="theme-default-content content__default"><p>归并排序的 javascript 实现。</p> <h1 id="归并排序"><a href="#归并排序" class="header-anchor">#</a> 归并排序</h1> <h2 id="排序问题"><a href="#排序问题" class="header-anchor">#</a> 排序问题</h2> <ul><li>输入：n 个数的一个序列<code>&lt;a1, a2, ..., an&gt;</code></li> <li>输出：输入序列的一个排列<code>&lt;a1', a2', ..., an'&gt;</code>，满足<code>a1' &lt;= a2' &lt;= ... &lt;= an'</code></li></ul> <h2 id="思路"><a href="#思路" class="header-anchor">#</a> 思路</h2> <p>假设桌面上有两堆扑克牌，每堆都已排序，最小的牌在上，把这两堆牌合并成单一的排好序的输出堆。</p> <p>对总输入堆进行处理：</p> <ol><li>将扑克牌分成两堆，每堆重复步骤 1~3 排序</li> <li>在牌面朝上的两堆牌的顶上两张牌中选取最小的一张，放置到输出堆</li> <li>重复步骤 2，直到一个输入堆为空</li> <li>将两堆扑克牌重复 2~3，合成输出堆</li></ol> <h2 id="js-实现"><a href="#js-实现" class="header-anchor">#</a> js 实现</h2> <div class="language-javascript extra-class"><pre class="language-javascript"><code><span class="token keyword">function</span> <span class="token function">mergeSort</span><span class="token punctuation">(</span><span class="token parameter">iArr</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token keyword">var</span> n <span class="token operator">=</span> iArr<span class="token punctuation">.</span>length<span class="token punctuation">;</span>
  <span class="token comment">// 若小于两位数，则按顺序排列后返回</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>n <span class="token operator">===</span> <span class="token number">2</span> <span class="token operator">&amp;&amp;</span> iArr<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">&gt;</span> iArr<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">return</span> <span class="token punctuation">[</span>iArr<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span> iArr<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>n <span class="token operator">&lt;=</span> <span class="token number">2</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">return</span> iArr<span class="token punctuation">;</span>
  <span class="token punctuation">}</span>
  <span class="token comment">// 若大于两位数，则分成两组，递归处理</span>
  <span class="token keyword">else</span> <span class="token punctuation">{</span>
    <span class="token keyword">var</span> p <span class="token operator">=</span> <span class="token function">parseInt</span><span class="token punctuation">(</span>n <span class="token operator">/</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">var</span> iArr1 <span class="token operator">=</span> <span class="token function">mergeSort</span><span class="token punctuation">(</span>iArr<span class="token punctuation">.</span><span class="token function">slice</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> p<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">var</span> iArr2 <span class="token operator">=</span> <span class="token function">mergeSort</span><span class="token punctuation">(</span>iArr<span class="token punctuation">.</span><span class="token function">slice</span><span class="token punctuation">(</span>p<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">var</span> oArr <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">if</span> <span class="token punctuation">(</span>iArr1<span class="token punctuation">.</span>length <span class="token operator">&amp;&amp;</span> iArr2<span class="token punctuation">.</span>length<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 比较最前两个数，取出较小的</span>
        oArr<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>
          iArr1<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">&lt;=</span> iArr2<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">?</span> iArr1<span class="token punctuation">.</span><span class="token function">splice</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">:</span> iArr2<span class="token punctuation">.</span><span class="token function">splice</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span>
        <span class="token punctuation">)</span><span class="token punctuation">;</span>
      <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
        <span class="token comment">// 若其中一组为空，则将另一组剩下的添加到输出尾部</span>
        oArr <span class="token operator">=</span> oArr<span class="token punctuation">.</span><span class="token function">concat</span><span class="token punctuation">(</span>iArr1<span class="token punctuation">.</span>length <span class="token operator">===</span> <span class="token number">0</span> <span class="token operator">?</span> iArr2 <span class="token operator">:</span> iArr1<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">break</span><span class="token punctuation">;</span>
      <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> oArr<span class="token punctuation">;</span>
  <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><h2 id="验证"><a href="#验证" class="header-anchor">#</a> 验证</h2> <div class="language-javascript extra-class"><pre class="language-javascript"><code><span class="token function">insertionSort</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">,</span> <span class="token number">6</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token comment">// 输出[1, 2, 3, 4, 5, 6]</span>

<span class="token function">insertionSort</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token comment">// 输出[1, 1, 2, 3, 5]</span>

<span class="token function">insertionSort</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">12</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">134</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">34</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">,</span> <span class="token number">6</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token comment">// 输出[1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 12, 34, 134]</span>
</code></pre></div></div> <!----> <footer class="page-edit"><div class="edit-link"><a href="https://github.com/godbasin/front-end-playground/edit/sourcecode/docs/front-end-addon/simple-algorithm/4-merge-sort.md" target="_blank" rel="noopener noreferrer">帮阿猪改善此页面！</a> <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></div> <!----> <blockquote>部分文章中使用了一些网站的截图，如果涉及侵权，请告诉我删一下谢谢~</blockquote> <div style="margin-top:30px;"><div class="el-row" style="margin-left:-10px;margin-right:-10px;"><div class="el-col el-col-24 el-col-sm-0 el-col-md-2 el-col-lg-4" style="padding-left:10px;padding-right:10px;display:block;"><div style="width:1px;height:1px;"></div></div> <div class="el-col el-col-24 el-col-sm-24 el-col-md-18 el-col-lg-16" style="padding-left:10px;padding-right:10px;"><div class="el-card box-card is-always-shadow"><div class="el-card__header"><div class="clearfix"><span>温馨提示喵</span></div></div><div class="el-card__body"> <div class="el-row" style="margin-left:-10px;margin-right:-10px;"><div class="el-col el-col-24 el-col-xs-24 el-col-sm-12" style="padding-left:10px;padding-right:10px;"><div class="el-image"><div class="image-slot"><img src="https://github-imglib-1255459943.cos.ap-chengdu.myqcloud.com/assets/img/loading.gif" style="width:100%;"></div><!----></div></div> <div class="el-col el-col-24 el-col-xs-24 el-col-sm-12" style="padding-left:10px;padding-right:10px;"><div class="copyright-text"><div>本文版权归作者所有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。</div> <div>出处：被删的前端游乐场</div> <div>作者：<a href="https://github.com/godbasin" target="_blank">被删</a></div></div></div></div></div></div></div></div></div></footer> <div class="page-nav"><p class="inner"><span class="prev">
        ←
        <a href="/front-end-playground/front-end-addon/simple-algorithm/3-insertion-sort.html" class="prev">
          3. 插入排序
        </a></span> <span class="next"><a href="/front-end-playground/front-end-addon/simple-algorithm/5-quick-sort.html">
          5. 快速排序
        </a>
        →
      </span></p></div>  <div class="gitalk-container theme-default-content"><div id="gitalk-container" class="content"></div></div></main> <div id="kitty-container"><span><div role="tooltip" id="el-popover-8067" aria-hidden="true" class="el-popover el-popper" style="width:undefinedpx;display:none;"><!----><img src="https://github-imglib-1255459943.cos.ap-chengdu.myqcloud.com/2code2.jpg" class="image"> <div class="text">牡羊猪的猫粮罐</div> </div><span class="el-popover__reference-wrapper"><div id="kitty" style="background:url(https://github-imglib-1255459943.cos.ap-chengdu.myqcloud.com/assets/img/kitty0.svg);"></div></span></span> <div class="el-dialog__wrapper" style="display:none;"><div role="dialog" aria-modal="true" aria-label="牡羊猪是这样渐渐胖成猪的喵（点击图片可以切换噢）" class="el-dialog" style="margin-top:15vh;"><div class="el-dialog__header"><span class="el-dialog__title">牡羊猪是这样渐渐胖成猪的喵（点击图片可以切换噢）</span><button type="button" aria-label="Close" class="el-dialog__headerbtn"><i class="el-dialog__close el-icon el-icon-close"></i></button></div><!----><!----></div></div></div></div><div class="global-ui"></div></div>
    <script src="/front-end-playground/assets/js/app.1e2670bf.js" defer></script><script src="/front-end-playground/assets/js/2.38d016d1.js" defer></script><script src="/front-end-playground/assets/js/3.e3f029cb.js" defer></script><script src="/front-end-playground/assets/js/21.6130b6a1.js" defer></script>
  </body>
</html>
